package com.yehui.algorithm.sort.impl;

import com.yehui.algorithm.sort.IntArraySort;

/**
 * 快排
 */
public class QuickSort implements IntArraySort {
    private void sort_0(int[] source, int start, int end) {
        if (source == null || source.length == 0) {
            return;
        }

        if (start >= end) {
            return;
        }

        int pivot = source[start];
        int low = start;
        int high = end;
        while (low < high) {
            while (low < high && source[high] >= pivot) {
                high--;
            }
            if (low < high) {
                source[low++] = source[high];
            }

            while (low < high && source[low] <= pivot) {
                low++;
            }
            if (low < high) {
                source[high--] = source[low];
            }
        }
        source[low] = pivot;
        sort_0(source, start, low - 1);
        sort_0(source, low + 1, end);
    }

    private void sort(int[] source, int start, int end) {
        if (start >= end) {
            return;
        }
        int partition = partition(source, start, end);
        sort(source, start, partition - 1);
        sort(source, partition + 1, end);
    }

    private int partition(int[] source, int start, int end) {
        int pivot = start;
        int index = pivot + 1;
        for (int i = index; i <= end; i++) {
            if (source[i] < source[pivot]) {
                swap(source, i, index++);
            }
        }
        swap(source, pivot, index - 1);
        return index - 1;
    }

    private void swap(int[] source, int left, int right) {
        int temp = source[left];
        source[left] = source[right];
        source[right] = temp;
    }

    /**
     * 排序
     *
     * @param source
     */
    @Override
    public void sort(int[] source) {
        sort(source, 0, source.length - 1);
    }
}
